package offer.day36;

public class No66Multiply {
    /*
     * 面试题66：构建乘积数组
     * 题目：给定一个数组A[0,1,2,...,n-1],请构建一个数组B[0,1,2,...,n-1],
     * 其中B中的元素B[i] =A[0]*A[1]*...*A[i-1]*A[i+1]*...A[n-1],不能使用除法
     *
     * 思路：
     *  B[0]   =   1  * A[1] * A[2] * ... * A[n-2] * A[n-1]
     *  B[1]   = A[0] *   1  * A[2] * ... * A[n-2] * A[n-1]
     *  B[2]   = A[0] * A[1] *   1  * ... * A[n-2] * A[n-1]
     *  ......
     *  B[n-2] = A[0] * A[1] * A[2] * ... *    1   * A[n-1]
     *  B[n-1] = A[0] * A[1] * A[2] * ... * A[n-2] *   1
     *
     * 然后对其进行上三角以及下三角区域相乘之积  即为所求
     * 上三角 由上到下计算
     * 下三角  由下到上计算
     *
     * */
    public static void main(String[] args) {
        No66Multiply m = new No66Multiply();
        int[] A = {1,2,3,4,3,2,1};
        int[] B = m.Multiply(A);
        for(int i = 0;i < A.length;i++) {
            System.out.println(B[i]+",");
        }
    }

    private int[] Multiply(int[] A) {
        if(A == null)
            return null;
        if(A.length == 0)
            return new int[0];
        int[] result = new int[A.length];
        result[0] = 1;
        //下三角C[i] = A[0]*A[1]*...*A[i-1]
        //由上到下顺序计算  C[i] = C[i-1]*A[i-1]
        //其中result[i]为C[i]
        for(int i = 1;i < A.length;i++)
            result[i] = result[i-1]*A[i-1];
        //上三角D[i] = A[i+1]*A[i+2]*...*A[n-1]
        //由下到上顺序计算 D[i] = D[i+1]*A[i+1]
        int temp = 1;
        //其中  从下到上
        //temp = A[A.length-1],
        //temp = A[A.length-1]*A[A.length-2]
        //,...,
        //temp = A[A.length-1]*A{A.length-2}*...*A[0]
        //result[i] = result[i] * temp  就是B{i]的结果		for(int i = A.length - 2; i >= 0;i--) {
        for(int i = A.length - 2;i >= 0;i--) {
            temp *= A[i + 1];
            result[i] *= temp;
        }
        return result;

    }

    private int[] Multiply2(int[] a) {
        if(a==null||a.length==0) return a;
        int[] B=new int[a.length];
        for(int i=0;i<a.length;i++){
            int x=1;
            int y=1;
            for(int j=0;j<=i-1;j++){
                x*=a[j];
            }
            for(int j=i+1;j<a.length;j++){
                y*=a[j];
            }
            B[i]=x*y;
        }
        return B;
    }
}
